package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/6 15:50
 * @Version 1.0
 **/
public class MergeIntervals {
    /**
     * 区间问题：
     * 贪心算法 -- 根据右节点排序，组合最大的区间
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        int lenx = intervals.length;
        ArrayList<Interval> list = new ArrayList<>();
        for (int i = 0; i < lenx; i++) {
            list.add(new Interval(intervals[i][0],intervals[i][1]));
        }
        intervals = null;
        Collections.sort(list);
        int right = list.get(0).right;
        int left = list.get(0).left;
        ArrayList<Interval> result = new ArrayList<>();
        for (int i = 1; i < lenx; i++) {
            if (list.get(i).left <= right) {
                right = Math.max(right,list.get(i).right);
            } else {
                result.add(new Interval(left,right));
                left = list.get(i).left;
                right = list.get(i).right;
            }
        }
        result.add(new Interval(left,right));
        list = null;
        int len = result.size();
        System.out.println(len);
        int resultArr[][] = new int[left][2];
        for (int i = 0; i < len; i++) {
            Interval interval = result.get(i);
            resultArr[i][0] = interval.left;
            resultArr[i][1] = interval.right;
        }
        return resultArr;
    }
}
class Interval implements Comparable<Interval> {
    int left, right;

    public Interval() {
    }

    public Interval(int left, int right) {
        this.left = left;
        this.right = right;
    }

    public int getLeft() {
        return left;
    }

    public void setLeft(int left) {
        this.left = left;
    }

    public int getRight() {
        return right;
    }

    public void setRight(int right) {
        this.right = right;
    }

    @Override
    public int compareTo(Interval o) {
        if (this.left < o.left) {
            return  -1;
        } else if (this.left > o.left) {
            return 1;
        } else {
            if (this.right > o.right) {
                return -1;
            } else if (this.right < o.right) {
                return 1;
            } else  {
                return 0;
            }
        }

    }
}
